package com.breeze.leetcode.interview;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

/**
 * https://leetcode-cn.com/problems/diving-board-lcci/
 * 面试题 16.11. 跳水板
 * 你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
 * <p>
 * 返回的长度需要从小到大排列。
 */
public class Solution1611 {
    /**
     * 第一版，通过TreeSet去重，并进行排序
     */
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) {
            return new int[0];
        }
        TreeSet<Integer> set = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        // i为shorter的个数，j为longer的个数
        for (int i = 0; i <= k; i++) {
            int j = k - i;
            set.add(i * shorter + j * longer);
        }

        int[] res = new int[set.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = set.pollFirst();
        }
        return res;
    }

    /**
     * 第二版：根据规律longer越多，和越大或者相等，故可以省略排序;通过记录上一次的和，如果两者相等则为重复，可以提高去重效率
     */
    public int[] divingBoard1(int shorter, int longer, int k) {
        if (k == 0) {
            return new int[0];
        }

        List<Integer> list = new ArrayList<>();
        int lastSum = 0;
        // x为longer的个数，y为shorter的个数
        for (int x = 0; x <= k; x++) {
            int y = k - x;
            int sum = x * longer + y * shorter;
            // 去重，且默认升序
            if (lastSum != sum) {
                list.add(sum);
                lastSum = sum;
            }
        }

        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    /**
     * 最终版
     * 1. 优化去重，重复的可能性只有一种就是shorter与longer相同，其单独处理
     * 2. 不相同的和个数为固定，股可以省去List转数组
     */
    public int[] divingBoard2(int shorter, int longer, int k) {
        if (k == 0) {
            return new int[0];
        }
        // shorter与longer相等时才会重复，且总数组只有一个值，就是 shorter*k
        if (shorter == longer) {
            return new int[]{shorter * k};
        }
        int[] res = new int[k + 1];

        for (int i = 0; i <= k; i++) {
            res[i] = i*longer+(k-i)*shorter;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution1611 solution1611 = new Solution1611();
        int[] ints = solution1611.divingBoard1(2, 2, 3);
        for (int anInt : ints) {
            System.out.print(anInt + ",");
        }
    }
}
